/**
 * 
 */
package com.gragra.sampling.nonproj.structures.nonprojective.singleroot;
import java.util.BitSet;
import java.util.concurrent.ConcurrentLinkedQueue;
import com.gragra.sampling.PopulationProbabilityAssigner;
import com.gragra.sampling.ThreadedUniformAccess;
import com.gragra.sampling.binary.ConvertSample;
import com.gragra.sampling.nonproj.ProposalDependencyAssigner;
import com.gragra.sampling.sequentialStructure.WordAndTagHolder;
/**
 * @author Christoph Teichmann
 * 15.10.2013
 */
public class GreedyWalkSingleRootNonProjDepdTree extends
		GreedySingleRootNonProj
{
	/**
	 * @param wth
	 * @param threads
	 * @param cs
	 */
	public GreedyWalkSingleRootNonProjDepdTree(WordAndTagHolder wth,
			int threads, ConvertSample cs)
	{super(wth, threads, cs);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.nonproj.structures.nonprojective.singleroot.GibbsGibbsSingleRootNonProjDepdTree#resampleAtPosition(int, com.gragra.sampling.PopulationProbabilityAssigner, double, int, com.gragra.sampling.ThreadedUniformAccess)
	 */
	@Override
	protected void resampleAtPosition(int pos,
			PopulationProbabilityAssigner pa, double annealing, int thread,
			ThreadedUniformAccess tua)
	{
		if(pos != this.getCurrentRoot(thread))
		{
			super.resampleAtPosition(pos, pa, annealing, thread, tua);
			return;
		}
		double oldProb = this.makeLogProbForThisConsideringAnnealing(pa, annealing, thread);
		int[] store = makeStorage(thread);
		BitSet bs = getSetFromPool();
		this.fillContainerWithChildren(pos, bs, thread);
		Chart c = this.fillChart(bs,pos,annealing,(ProposalDependencyAssigner) pa,thread);
		double correction = getProbFromChart(bs, c, thread);
		drawFromChart(bs, c , pos, thread, tua);
		correction -= getProbFromChart(bs, c, thread);
		double newProb = this.makeLogProbForThisConsideringAnnealing(pa, annealing, thread);
		if(Math.log(tua.nextDouble(thread)) > newProb-oldProb+correction)
		{restore(store,thread);}
		else
		{this.returnStorage(store);}
		returnToPool(bs);
		returnChart(c);
	}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.nonproj.structures.nonprojective.singleroot.SingleRootNonProjDepdTree#skip(int, com.gragra.sampling.PopulationProbabilityAssigner, int)
	 */
	@Override
	protected boolean skip(int pos, PopulationProbabilityAssigner pa, int thread)
	{return false;}
	/**
	 * 
	 * @param store
	 * @param thread
	 */
	private void restore(int[] store, int thread)
	{
		for(int i=0;i<this.getLength();++i)
		{this.setNewHead(i, store[i], thread);}
		returnStorage(store);
	}
	/**
	 * 
	 */
	private final static ConcurrentLinkedQueue<int[]> storageStorage = new ConcurrentLinkedQueue<int[]>();
	/**
	 * 
	 * @param store
	 */
	private void returnStorage(int[] store)
	{storageStorage.add(store);}
	/**
	 * 
	 * @param thread
	 * @return
	 */
	private int[] makeStorage(int thread)
	{
		int[] store = storageStorage.poll();
		if(store == null || store.length < this.getLength())
		{store = new int[this.getLength()];}
		for(int i=0;i<this.getLength();++i)
		{store[i] = this.getHeadPosition(i, thread);}
		return store;
	}
	/**
	 * 
	 * @param bs
	 * @param c
	 * @param pos
	 * @param thread
	 * @param tua 
	 */
	private void drawFromChart(final BitSet bs, Chart c, int pos, int thread, ThreadedUniformAccess tua)
	{
		BitSet seen = this.getSetFromPool();
		seen.set(pos);
		BitSet toDo = this.getSetFromPool();
		toDo.or(bs);
		while(!toDo.isEmpty())
		{
			int start = drawRandom(toDo,thread,tua);
			int point = start;
			while(!seen.get(point))
			{
				int next = drawRandom(point,bs,pos,c,thread,tua);
				this.setNewHead(point, next, thread);
				point = next;
			}
			point = start;
			while(!seen.get(point))
			{
				seen.set(point);
				toDo.clear(point);
				point = this.getHeadPosition(point, thread);
			}
		}
		this.returnToPool(toDo);
		this.returnToPool(seen);
	}
	/**
	 * 
	 * @param point
	 * @param bs
	 * @param pos
	 * @param c
	 * @param thread
	 * @param tua
	 * @return
	 */
	private int drawRandom(int point, BitSet bs, int pos, Chart c, int thread,
			ThreadedUniformAccess tua)
	{
		double border = tua.nextDouble(thread);
		int choice = -1;
		for(int head=bs.nextSetBit(0);head>=0;head=bs.nextSetBit(head+1))
		{
			border -= c.transitionProbs[point][head];
			if(border <= 0.0)
			{
				choice = head;
				break;
			}
		}
		if(border > 0.0)
		{
			border -= c.transitionProbs[point][pos];
			if(border <= 0.0)
			{choice = pos;}
			else
			{throw new IllegalStateException("Probabilities did not sum to one.");}
		}
		return choice;
	}
	/**
	 * 
	 * @param toDo
	 * @param thread
	 * @param tua
	 * @return
	 */
	private int drawRandom(BitSet toDo, int thread, ThreadedUniformAccess tua)
	{
		int head=-1;
		int choice = tua.nextInt(thread, 1, toDo.cardinality());
		for(;choice>0;--choice)
		{head = toDo.nextSetBit(head+1);}
		return head;
	}
	/**
	 * 
	 * @param bs
	 * @param c 
	 * @param thread
	 * @return
	 */
	private double getProbFromChart(BitSet bs, Chart c, int thread)
	{
		double d = 0.0;
		for(int child=bs.nextSetBit(0);child>=0;child=bs.nextSetBit(child+1))
		{d += Math.log(c.transitionProbs[child][this.getHeadPosition(child, thread)]);}
		return d;
	}
	/**
	 * 
	 * @param bs
	 * @param pos
	 * @param annealing
	 * @param pa 
	 * @param thread
	 * @return
	 */
	private Chart fillChart(BitSet bs, int pos, double annealing, ProposalDependencyAssigner pa, int thread)
	{
		Chart c = this.getChart();
		for(int child=bs.nextSetBit(0);child>=0;child=bs.nextSetBit(child+1))
		{
			double max = Double.NEGATIVE_INFINITY;
			for(int headCandidate=bs.nextSetBit(0);headCandidate>=0;headCandidate=bs.nextSetBit(headCandidate+1))
			{
				if(headCandidate == child)
				{c.transitionProbs[child][headCandidate] = Double.NEGATIVE_INFINITY;}
				else
				{max = Math.max(max,c.transitionProbs[child][headCandidate] = makeApproximationWithAnnealing(annealing, pa, thread, child, headCandidate));}
			}
			max = Math.max(max,c.transitionProbs[child][pos] = makeApproximationWithAnnealing(annealing, pa, thread, child, pos));
			double sum = 0.0;
			for(int headCandidate=bs.nextSetBit(0);headCandidate>=0;headCandidate=bs.nextSetBit(headCandidate+1))
			{sum +=  c.transitionProbs[child][headCandidate] = Math.exp(c.transitionProbs[child][headCandidate]-max);}
			sum +=  c.transitionProbs[child][pos] = Math.exp(c.transitionProbs[child][pos]-max);
			for(int headCandidate=bs.nextSetBit(0);headCandidate>=0;headCandidate=bs.nextSetBit(headCandidate+1))
			{c.transitionProbs[child][headCandidate] /= sum;}
			c.transitionProbs[child][pos] /= sum;
		}
		return c;
	}
	/**
	 * @param annealing
	 * @param pa
	 * @param thread
	 * @param child
	 * @param headCandidate
	 * @return
	 */
	protected double makeApproximationWithAnnealing(double annealing,
			ProposalDependencyAssigner pa, int thread, int child,
			int headCandidate)
	{
		return pa.makeChartProposalProb(this, headCandidate, child, thread)*annealing;
	}
	/**
	 * 
	 * @param bs
	 */
	private void returnToPool(BitSet bs)
	{bsPool.add(bs);}
	/**
	 * 
	 */
	private final static ConcurrentLinkedQueue<BitSet> bsPool = new ConcurrentLinkedQueue<BitSet>();
	/**
	 * 
	 * @return
	 */
	private BitSet getSetFromPool()
	{
		BitSet ret = bsPool.poll();
		if(ret == null)
		{ret = new BitSet();}
		ret.clear();
		return ret;
	}
	/**
	 * 
	 */
	private final static ConcurrentLinkedQueue<Chart> chartPool = new ConcurrentLinkedQueue<GreedyWalkSingleRootNonProjDepdTree.Chart>();
	/**
	 * 
	 * @param c
	 */
	private void returnChart(Chart c)
	{chartPool.add(c);}
	/**
	 * 
	 * @return
	 */
	private Chart getChart()
	{
		Chart ret = chartPool.poll();
		if(ret == null)
		{ret = new Chart();}
		ret.ensureSize(this.getLength());
		return ret;
	}
	/**
	 * 
	 * @author Christoph Teichmann
	 * 15.10.2013
	 */
	private class Chart
	{
		/**
		 * 
		 */
		private double[][] transitionProbs;
		/**
		 * 
		 */
		private int s = 0;
		/**
		 * 
		 * @param size
		 */
		private void ensureSize(int size)
		{
			if(this.s < size)
			{
				this.s = size;
				transitionProbs = new double[size][size+1];
			}
		}
	}
}